package arithmetic.LeetCode;

import java.util.Arrays;
import java.util.Stack;

import org.junit.jupiter.api.Test;

/**
 *
 * @author jiangfeng on 2023/4/17
 */
public class DailyTemperatures {
    @Test
    public  void main() {
        System.out.println(Arrays.toString(dailyTemperatures(new int[] {73, 74, 75, 71, 69, 72, 76, 73})));

    }
    // 思路:单调栈. 单调递减,表示出栈时表示,右边第一个比他大的数,谁让他出,谁比他大
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack();
        int[] result = new int[temperatures.length];
        stack.push(0);
        int i=1;
        while(i<temperatures.length){
            while (stack.isEmpty() || (i < temperatures.length && temperatures[stack.peek()] > temperatures[i])) {
                stack.push(i++);
            }
            while (!stack.isEmpty() && i < temperatures.length && temperatures[stack.peek()] < temperatures[i]) {
                int d = stack.pop();
                result[d] = i-d;
            }
        }
        result[temperatures.length - 1] = 0;
        return result;
    }
}
